{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Matrix product state overview\n",
    "\n",
    "### Contributors\n",
    "\n",
    "Merav Aharoni$^{1}$, Elad Goldman$^{1}$, Yehuda Naveh$^{1}$ and Yotam Vaknin$^{1}$\n",
    "\n",
    "1. IBM Research Haifa, Haifa University Campus, Mount Carmel Haifa, Israel\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction\n",
    "`Tensor networks` are used as an alternate representation for a network of qubits. This representation consists of a network of tensors with connections among them. The `matrix product state` (MPS) is the simplest type of tensor network, where we have a one dimensional set of tensors, with connections between every two consecutive tensors. This representation can be used to represent a system of qubits, where each qubit is represented by one tensor. The MPS structure is often depicted graphically, as follows: \n",
    "![](images/mps.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The concept of `matrix product state`was initially proposed in [1], to the best of our knowledge.  There are other papers that describe the structure in more detail, for example [2].\n",
    "\n",
    "A pure quantum state is usually described as a state vector, by the expression $|\\psi\\rangle =  \\sum_{i_1=0}^1 {\\ldots} \\sum_{i_n=0}^1 c_{i_1 \\ldots i_n} |i_i\\rangle {\\otimes} {\\ldots} {\\otimes} |i_n\\rangle$.\n",
    "\n",
    "The state vector representation implies an exponential size representation, regardless of the actual circuit. Every quantum gate operating on this representation requires exponential time and memory.\n",
    "\n",
    "The matrix product state reprentation offers a local representation, in the form:\n",
    "$\\Gamma^{[1]} \\lambda^{[1]} \\Gamma^{[2]} \\lambda^{[2]}\\ldots \\Gamma^{[1]} \\lambda^{[n-1]} \\Gamma^{[n]}$. The $c_{i_1 \\ldots i_n}$ can be computed from this structure.  \n",
    "\n",
    "Every $\\Gamma^{[i]}$ is a tensor of complex numbers that represents qubit $i$. Every $\\lambda^{[i]}$ is a matrix of real numbers that is used to normalize the amplitudes of qubits $i$ and $i+1$. \n",
    "\n",
    "Gate operations can be performed by local operations on the relevant $\\Gamma$s. Computations such as expectation value can also be obtained by operations on the relevant $\\Gamma$s, without need to compute the full state vector. Measurement on a single qubit can also be performed locally on the respective $\\Gamma$, but its effect must be propagated to the remaining qubits to preserve the effects of entanglement.\n",
    "\n",
    "We implemented MPS as a simulation method in the qasm simulator. In our implementation, every tensor $\\Gamma^{[i]}$ is represented as a pair of matrices $\\Gamma^{[i]}[0]$ and $\\Gamma^{[i]}[1]$, that are used to represent the amplitudes of $|0\\rangle$ and $|1\\rangle$ respectively.\n",
    "\n",
    "Single-qubit gates operate only on the relevant tensor. For example, the Pauli-$X$ gate is implemented by simply swapping between $\\Gamma^{[i]}[0]$ and $\\Gamma^{[i]}[1]$\n",
    "\n",
    "Two-qubit gates operate on consecutive qubits $i$ and $i+1$. This involves a contract operation over $\\lambda^{[i-1]}$, $\\Gamma^{[i-1]}$, $\\lambda^{[i]}$, $\\Gamma^{[i+1]}$ and  $\\lambda^{[i+1]}$, that creates a single tensor. In our implementation, this tensor consists of four matrices: $\\Gamma^{[i, i+1]}[00]$, $\\Gamma^{[i, i+1]}[01]$, $\\Gamma^{[i, i+1]}[10]$ and $\\Gamma^{[i, i+1]}[11]$.\n",
    "\n",
    "We apply the gate to this tensor, and then decompose back to the original structure, using singular value decomposition (SVD). SVD decomposes the tensor into three matrices $U S V^{\\dagger}$, such that $U$ and $V$ are complex unitary matrices, and $S$ is a diagonal matrix of real numbers, where some of the entries on the diagonal may be $0$. The number of non-zero entries on this diagonal is named the `Schmidt coefficient`. Following a normalization step by dividing into $\\lambda^{[i-1]}$ and $\\lambda^{[i+1]}$ respectively, $U$ becomes $\\Gamma^{[i]}$, $V$ becomes $\\Gamma^{[i+1]}$. $S$ becomes the new $\\lambda^{[i]}$.\n",
    "\n",
    "Note that two-qubit operations may increase the size of the respective tensors. The sizes are determined by the Schmidt coefficient. Intuitively, the Schmidt coefficients provide a measurement of the entanglement of the system, and therefore determine the performance of the circuit.\n",
    "\n",
    "Gates that involve two qubits that are not consecutive, require a series of swap gates to bring the two qubits next to each other and then the reverse swaps, to bring the qubits back to their original positions. \n",
    "\n",
    "In the worst case, the tensors may grow exponentially. However, the size of the overall structure remains 'small' for circuits that do not have 'many' two-qubit gates. This allows much more efficient operations in circuits with relatively 'low' entanglement. Characterizing when to use this method over other methods is a subject of current research.\n",
    "\n",
    "We referred to several additional papers, for example [3], [4], [5] to provide further insight into understanding and implementing MPS as a simulation method in Qiskit."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "1. G. Vidal, *Efficient classical simulation of slightly entangled quantum computations*, Phys. Rev. Lett. 91 (2003) 147902, https://arxiv.org/abs/quant-ph/0301063.\n",
    "\n",
    "2. U. Schollwöck, *The density-matrix renormalization group in the age of matrix product states*, Annals of Physics 326 (1) (2011) 96 - 192, january 2011, Special Issue, https://arxiv.org/abs/1008.3477.\n",
    "\n",
    "3. R. Orús, *A practical introduction to tensor networks: Matrix product states and projected entangled pair states*, Annals of Physics 349 (2014) 117 - 158, https://arxiv.org/abs/1306.2164.\n",
    "\n",
    "4. J. Biamonte and V. Bergholm, *Tensor networks in a nutshell*, https://arxiv.org/abs/1306.2164.\n",
    "\n",
    "5. D. Jaschke, M. L. Walla, L. D. Carr, *Open source Matrix Product States: Opening ways to simulate entangled many-body quantum systems in one dimension*, Computer Physics Communications 225, 59-91, https://arxiv.org/abs/1703.00387."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Using the matrix product state simulation method\n",
    "The matrix product state simulation method is invoked in the qasm simulator by setting the `simulation_method` in the qasm_simulator to 'matrix_product_state'.\n",
    "We demonstrate this using simple use-cases in the tutorial `matrix_product_state_simulation_method`.\n",
    "\n",
    "As we show there, performance of circuits using the MPS simulation method can be much more efficient than using the Statevector simulation method, as long as:\n",
    "1. The internal data structures don't grow too much, i.e., entanglement is not too high.\n",
    "2. We do not wish to compute the state vector, nor all the amplitudes, because this computation is always exponential in the number of qubits.\n",
    "\n",
    "We demonstrate this in the following graph. We ran these two simulation methods on a set of randomly generated circuits, where the percentage of two-qubit gates is 0.1. The depth of the circuits is kept constant at 120 gates. The final computation of the circuit is the expectation value of random Pauli gates on 5 random qubits.\n",
    "\n",
    "![](images/graph_of_random_circuits.jpg)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
